package com.example.algorithm.service.impl;

import com.example.algorithm.service.BacktrackingService;
import lombok.extern.slf4j.Slf4j;
import org.springframework.stereotype.Service;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/** 回溯
 * 思路
 * ①画出递归树，找到状态变量(回溯函数的参数)，这一步非常重要※
 * ②根据题意，确立结束条件
 * ③找准选择列表(与函数参数相关),与第一步紧密关联※
 * ④判断是否需要剪枝
 * ⑤作出选择，递归调用，进入下一层
 * ⑥撤销选择
 *
 *
 * @auth Administrator
 * @create @2024/7/31@21:34
 * @decription
 **/
@Service
@Slf4j
public class BacktrackingServiceImpl implements BacktrackingService {
    /**
     * NO.54 全排列
     *
     * 给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
     * @param nums
     * @return
     * 解法一：回溯(递归)
     *
     *
     *
     */
    @Override
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        subPermute(nums,result,new ArrayList<>());
        return result;
    }



    /**
     * 回溯
     * @param nums
     * @param result
     * @param tmp
     */
    public void subPermute(int []nums,List<List<Integer>> result,List<Integer>tmp){
        if(tmp.size()== nums.length){
            result.add(new ArrayList<>(tmp));
            return;
        }
        for(int i=0;i< nums.length;i++){
            if(!tmp.contains(nums[i])){
                tmp.add(nums[i]);
                subPermute(nums,result,tmp);
                tmp.remove(tmp.size()-1);
            }
        }
    }


    /** NO.55 子集
     * 给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的
     * 子集
     * （幂集）。
     *
     * 解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
     * @param nums
     * @return
     * 解法一：迭代
     * 解法二：回溯
     * 解法三：DFS
     *
     */
    @Override
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        LinkedList<Integer> path = new LinkedList<>();
        subSubsets(nums,result,path,0);
        return result;
    }



    /**
     * 回溯
     * @param nums
     * @param result
     * @param path
     */
    public void subSubsets(int []nums,List<List<Integer>> result,LinkedList<Integer> path,int startIndex){
        result.add(new ArrayList<>(path));
        if(startIndex>= nums.length){
            return;
        }
        for(int i=startIndex;i< nums.length;i++){
            path.add(nums[i]);
            subSubsets(nums,result,path,i+1);
            path.removeLast();
        }
    }

    /**NO.56 电话号码的字母组合
     * 给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
     *
     * 给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
     * @param digits
     * @return
     * 解法一：回溯+哈希表
     * 解法二：队列
     * 解法三：递归
     *
     */
    @Override
    public List<String> letterCombinations(String digits) {
        List<String> result = new ArrayList<>();
        StringBuffer sb = new StringBuffer();
        if(digits==null||digits.length()==0){
            return result;
        }
        subLetterCombinations(digits,result,sb,0);
        return result;
    }



    /**
     * 回溯
     * @param digits
     * @param result
     * @param startIndex
     */
    public void subLetterCombinations(String digits,List<String> result,StringBuffer sb ,int startIndex){

        if(startIndex== digits.length()){
            result.add(sb.toString());
            return;
        }
        String[] numString = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        String str = numString[digits.charAt(startIndex)-'0'];
        for(int i=0;i< str.length();i++){
            sb.append(str.charAt(i));
            subLetterCombinations(digits,result,sb,startIndex+1);
            sb.deleteCharAt(sb.length()-1);
        }
    }

    /**NO.57 组合总和
     * 给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
     *
     * candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
     *
     * 对于给定的输入，保证和为 target 的不同组合数少于 150 个
     * @param candidates
     * @param target
     * @return
     * 解法一：选或不选
     * 解法二：枚举选哪个
     * 解法三：完全背包预处理 + 可行性剪枝
     *
     */
    @Override
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> tmp = new ArrayList<>();
        Arrays.sort(candidates);
        if(candidates.length==0){
            return res;
        }
        subCombinationSum(candidates,res,tmp,target,0);
        return res;
    }




    /**
     * 回溯
     * @param candidates
     * @param res
     * @param tmp
     * @param startIndex
     */
    public void subCombinationSum(int[] candidates,List<List<Integer>> res,List<Integer> tmp ,int target,int startIndex){
        if(startIndex==candidates.length){
            return;
        }
        // 子集和等于 target 时，记录解
        if(target==0){
            res.add(new ArrayList<>(tmp));
            return;
        }
        // 剪枝二：从 start 开始遍历，避免生成重复子集
        for(int i=startIndex;i< candidates.length;i++){
            // 剪枝一：若子集和超过 target ，则直接结束循环
            // 这是因为数组已排序，后边元素更大，子集和一定超过 target
            if(target-candidates[i]<0){
                break;
            }
            // 尝试：做出选择，更新 target, start
            tmp.add(candidates[i]);
            // 进行下一轮选择
            subCombinationSum(candidates,res,tmp,target-candidates[i],i);
            // 回退：撤销选择，恢复到之前的状态
            tmp.remove(tmp.size()-1);
        }
    }

    /**NO.58 括号生成
     * 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
     * @param n
     * @return
     * 解法一：暴力匹配，递归
     * 解法二：回溯法
     * 解法三：按括号序列的长度递归
     * 解法四：动态规划
     * 解法五：深度优先算法
     * 解法六：广度优先算法
     *
     */
    @Override
    public List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<>();
        StringBuffer sb = new StringBuffer();
        subEenerateParenthesis(n,result,sb,n,n);
        return result;
    }




    /**
     *  回溯
     * @param n
     * @param result
     * @param sb
     * @param left
     * @param right
     */
    public void subEenerateParenthesis(int n,List<String> result,StringBuffer sb ,int left,int right){
        if(left==0&&right==0){
            result.add(sb.toString());
            return;
        }
        if(left>right){
            return;
        }
        if(left>0){
            subEenerateParenthesis(n,result, sb.append("("),left-1,right);
            sb.deleteCharAt(sb.length()-1);
        }
        if(left<right){
            subEenerateParenthesis(n,result, sb.append(")"),left,right-1);
            sb.deleteCharAt(sb.length()-1);
        }
    }

    /**NO.59 单词搜索
     * 给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
     *
     * 单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
     *
     * @param board
     * @param word
     * @return
     * 解法一：回溯
     * 解法二：深度优先搜索（DFS）+ 剪枝
     *
     *
     */
    boolean result = false;
    @Override
    public boolean exist(char[][] board, String word) {
      boolean[][] visited = new boolean[board.length][board[0].length];

        for(int xRay=0;xRay<board.length;xRay++){
            for(int yRay=0;yRay< board[0].length;yRay++){
                if(word.indexOf(board[xRay][yRay])==-1){
                    continue;
                }
                subExist(board,word,visited,xRay,yRay,0);
                if(result){
                    break;
                }
            }
        }
        return result;
    }



    /**
     * 回溯
     * @param board
     * @param word
     * @param xRay
     * @param yRay
     */
    public void subExist(char[][] board,String word, boolean[][] visited,int xRay,int yRay,int index){
        if(index==word.length()){
            result=true;
            return;
        }
        if(xRay>=board.length||yRay>=board[0].length||xRay<0||yRay<0||visited[xRay][yRay]){
            return ;
        }

        if(word.charAt(index)!=board[xRay][yRay]){
            return;
        }
        visited[xRay][yRay]=true;
        subExist(board,word,visited,xRay-1,yRay,index+1);
        subExist(board,word,visited,xRay+1,yRay,index+1);
        subExist(board,word,visited,xRay,yRay-1,index+1);
        subExist(board,word,visited,xRay,yRay+1,index+1);
        visited[xRay][yRay]=false;
    }

    /**NO.60 分割回文串
     * 给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是
     * 回文串
     *  。返回 s 所有可能的分割方案。
     * @param s
     * @return
     * 解法一：回溯 + 动态规划预处理
     * 解法二：回溯 + 记忆化搜索
     *
     */
    @Override
    public List<List<String>> partition(String s) {
        List<List<String>> result = new ArrayList<>();
        List<String>tmp = new ArrayList<>();
        subPartition(s,result,tmp);
        return result;
    }




    /**
     * 回溯
     * @param s
     * @param result
     * @param tmp
     */
    public void subPartition(String s,List<List<String>> result,List<String>tmp){
        if(s.length()==0){
            result.add(new ArrayList<>(tmp));
            return;
        }
        for(int i=0;i< s.length();i++){
            String str = s.substring(0,i+1);
            if(!isPalindrome(str)){
                continue;
            }
            tmp.add(str);
            subPartition(s.substring(i+1),result,tmp);
            tmp.remove(tmp.size()-1);
        }
    }


    /**
     * 回文串
     * @param str
     * @return
     */
    public boolean isPalindrome(String str) {
        if (str == null || str.length() == 0) {
            return true;
        }
        String reversedStr = new StringBuilder(str).reverse().toString();
        return str.equals(reversedStr);
    }

    /**NO.61 N皇后
     * 按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
     *
     * n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
     *
     * 给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
     *
     * 每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
     * @param n
     * @return
     * 解法一：基于集合回溯
     * 解法二：基于位运算的回溯
     */


    @Override
    public List<List<String>> solveNQueens(int n) {
        char[][] matrix = new char[n][n];
        for(int i=0;i<n;i++){
            Arrays.fill(matrix[i],'.');
        }
        List<List<String>> queResult = new ArrayList<>();
        subSolveNQueens(matrix,queResult,0,n);
        return queResult;
    }

    /**
     * 回溯
     * @param matrix
     * @param xRay
     */
    public void subSolveNQueens(char[][] matrix,  List<List<String>> queResult,int xRay,int n){
         if(xRay==n){
             queResult.add(array2List(matrix));
             return;
         }
         for(int yRay=0;yRay<n;yRay++){
             if(checkQueue(matrix,xRay,yRay)){
                 matrix[xRay][yRay]='Q';
                 subSolveNQueens(matrix,queResult,xRay+1,n);
                 matrix[xRay][yRay]='.';
             }
         }
    }


    /**
     * 校验是否可以为皇后
     * @param matrix
     * @return
     */
    private boolean checkQueue(char[][] matrix ,int xRay ,int yRay){
     //检查列
        for(int i=0;i<xRay;i++){
            if('Q'==matrix[i][yRay]){
                return false;
            }
        }
    //检查45角变
        for(int i=xRay-1,j=yRay-1;i>=0&&j>=0;i--,j--){
            if('Q'==matrix[i][j]){
                return false;
            }
        }
        //检查135角变
        for(int i=xRay-1,j=yRay+1;i>=0&&j<matrix.length;i--,j++){
            if('Q'==matrix[i][j]){
                return false;
            }
        }
        return true;
    }

    /**
     * 数组与列表转换
     * @param matrix
     * @return
     */
    public List<String> array2List(char[][] matrix) {
        List<String> list = new ArrayList<>();

        for (char[] str : matrix) {
            list.add(String.copyValueOf(str));
        }
        return list;
    }

}
